package a07_二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a25_二叉搜索树中的众数复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/17
 */
public class a25_二叉搜索树中的众数复习3 {

    public static void main(String[] args) {
        a25_二叉搜索树中的众数复习3 test = new a25_二叉搜索树中的众数复习3();
        TreeNode treeNode = new TreeNode(1,
                null,
                new TreeNode(2));
        int[] mode = test.findMode(treeNode);
        System.out.println(Arrays.toString(mode));
    }

    public int[] findMode(TreeNode root) {
        traversal(root);
        return result.stream().mapToInt(i -> i).toArray();
    }

    TreeNode prevNode = null;
    int curCount = 0;
    int maxCount = 0;
    List<Integer> result = new ArrayList<>();

    private void traversal(TreeNode node){
        if (node == null) {
            return;
        }
        traversal(node.left);

        if (prevNode == null) {//第一个元素
            prevNode = node;
            curCount = 1;

            maxCount = 1;
            result.add(node.val);
        }else {//不是第一个元素
            if(node.val == prevNode.val){//前一个元素和当前元素相等
                prevNode = node;
                curCount++;
                if(curCount == maxCount){
                    result.add(node.val);
                }else if(curCount > maxCount){
                    result.clear();
                    maxCount = curCount;
                    result.add(node.val);
                }
            }else {//前一个元素和当前元素不相等
                prevNode = node;
                curCount = 1;
                if(curCount == maxCount){
                    result.add(node.val);
                }else if(curCount > maxCount){
                    result.clear();
                    maxCount = curCount;
                    result.add(node.val);
                }
            }
        }

        traversal(node.right);
    }
}
